class node():
    def __init__(self, char='I', f=0, left=None, rigt=None):
        self.c = char
        self.f = f
        self.left = left
        self.rigt = rigt
    def __str__(self):
        return str(self.c) + ':' + str(self.f)
    def __lt__(self, other):
        return self.f < other.f

def huffman(C, D):
    n = len(C)
    Q = [node(char=d,f=c) for (c,d) in zip(C,D)]
    heapify(Q)
    for i in xrange(n - 1):
        x = heappop(Q)
        y = heappop(Q)
        z = node(f=x.f+y.f, left=x, rigt=y)
        heappush(Q, z)
    return heappop(Q)

X = []
def dfs(r):
    if r.left is None and r.rigt is None:
        print r.c, ':', X        
    if r.left is not None:
        X.append('0')
        dfs(r.left)
        X.pop()
    if r.rigt is not None:
        X.append('1')
        dfs(r.rigt)
        X.pop()

if __name__ == '__main__':
    from heapq import heapify, heappush, heappop
    C = [45,13,12,16,9,6]
    D = ['a','b','c','d','e','f']
    r = huffman(C, D)
    dfs(r)
